# 41/100 二叉树-二叉树的层序遍历
# leetcode第102题: https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/10
from typing import Optional
from collections import deque
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    queue = deque([root])

    res = []
    while queue:
        n = len(queue)
        lc = []
        for i in range(n):
            cur = queue.popleft()
            lc.append(cur.val)
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        res.append(lc)
    return res


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([4, 2, 7, 1, 3, 6, 9])
    t2 = TreeConverter.list_to_tree([2, 1, 3])
    t3 = None
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, ]
    out = [[[4], [2, 7], [1, 3, 6, 9]],
           [[2], [1, 3]], [], ]
    test.test_function(levelOrder, inp, out)
